package com.lc.projects.years.question2016.month07;

/**
 * LeetCode Write a program to find the n-th ugly number.
 * 
 * Ugly numbers are positive numbers whose prime factors only include 2, 3, 5.
 * For example, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10
 * ugly numbers.
 * 
 * Note that 1 is typically treated as an ugly number.
 * 
 * @author user
 *
 */
public class Test1GetUglyNum {
	public static void main(String[] args) {
		Test1GetUglyNum t1 = new Test1GetUglyNum();
		System.out.println(t1.nthUglyNumber(9));
	}

	public int nthUglyNumber(int n) {
		int i = 1;
		int num = 1;
		while (true) {
			if (isUglyNum(num)) {
				if (i == n) {
					break;
				}
				i++;
			}
			num++;
		}

		return num;
	}

	private boolean isUglyNum(int num) {
		if (num == 1) {
			return true;
		}

		if (num % 2 == 0) {
			return isUglyNum(num / 2);
		} else if (num % 3 == 0) {
			return isUglyNum(num / 3);
		} else if (num % 5 == 0) {
			return isUglyNum(num / 5);
		} else {
			return false;
		}

	}

}
